package com.sxkiler.demo.medium;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import java.util.*;
import com.sxkiler.demo.model.*;

/**
longest-palindromic-subsequence=最长回文子序列
<p>给定一个字符串 <code>s</code> ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 <code>s</code> 的最大长度为 <code>1000</code> 。</p>

<p>&nbsp;</p>

<p><strong>示例 1:</strong><br>
输入:</p>

<pre>"bbbab"
</pre>

<p>输出:</p>

<pre>4
</pre>

<p>一个可能的最长回文子序列为 "bbbb"。</p>

<p><strong>示例 2:</strong><br>
输入:</p>

<pre>"cbbd"
</pre>

<p>输出:</p>

<pre>2
</pre>

<p>一个可能的最长回文子序列为 "bb"。</p>

<p>&nbsp;</p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s</code> 只包含小写英文字母</li>
</ul>

 */
public class longestPalindromeSubseq {


    /**
     思路与算法

     对于一个子串而言，如果它是回文串，并且长度大于 222，那么将它首尾的两个字母去除之后，它仍然是个回文串。
     例如对于字符串 “ababa”\textrm{``ababa''}“ababa”，如果我们已经知道 “bab”\textrm{``bab''}“bab” 是回文串，那么 “ababa”\textrm{``ababa''}“ababa” 一定是回文串，这是因为它的首尾两个字母都是 “a”\textrm{``a''}“a”。

     根据这样的思路，我们就可以用动态规划的方法解决本题。我们用 P(i,j)P(i,j)P(i,j) 表示字符串 sss 的第 iii 到 jjj 个字母组成的串（下文表示成 s[i:j]s[i:j]s[i:j]）是否为回文串：

     P(i,j)={true,如果子串 Si…Sj 是回文串false,其它情况P(i,j) = \begin{cases} \text{true,} &\quad\text{如果子串~} S_i \dots S_j \text{~是回文串}\\ \text{false,} &\quad\text{其它情况} \end{cases} P(i,j)={true,false,​如果子串 Si​…Sj​ 是回文串其它情况​

     这里的「其它情况」包含两种可能性：

     s[i,j]s[i, j]s[i,j] 本身不是一个回文串；

     i>ji > ji>j，此时 s[i,j]s[i, j]s[i,j] 本身不合法。

     那么我们就可以写出动态规划的状态转移方程：

     P(i,j)=P(i+1,j−1)∧(Si==Sj)P(i, j) = P(i+1, j-1) \wedge (S_i == S_j) P(i,j)=P(i+1,j−1)∧(Si​==Sj​)

     也就是说，只有 s[i+1:j−1]s[i+1:j-1]s[i+1:j−1] 是回文串，并且 sss 的第 iii 和 jjj 个字母相同时，s[i:j]s[i:j]s[i:j] 才会是回文串。

     上文的所有讨论是建立在子串长度大于 222 的前提之上的，我们还需要考虑动态规划中的边界条件，即子串的长度为 111 或 222。对于长度为 111 的子串，它显然是个回文串；对于长度为 222 的子串，只要它的两个字母相同，它就是一个回文串。因此我们就可以写出动态规划的边界条件：

     {P(i,i)=trueP(i,i+1)=(Si==Si+1)\begin{cases} P(i, i) = \text{true} \\ P(i, i+1) = ( S_i == S_{i+1} ) \end{cases} {P(i,i)=trueP(i,i+1)=(Si​==Si+1​)​

     根据这个思路，我们就可以完成动态规划了，最终的答案即为所有 P(i,j)=trueP(i, j) = \text{true}P(i,j)=true 中 j−i+1j-i+1j−i+1（即子串长度）的最大值。注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。
     */
    public class SolutionC{
        public String longestPalindrome(String s) {
            int len = s.length();
            if (len < 2) {
                return s;
            }
            int maxLen = 1;
            int begin = 0;
            //初始化
            boolean[][] dp = new boolean[len][len];
            for(int i=0;i<len;i++){
                dp[i][i] = true;
            }
            char[] charArray = s.toCharArray();
            for(int step=2;step<=len;step++){
                for(int i=0;i<len;i++){
                    int j = i + step - 1;
                    if(j>=len)break;
                    if(charArray[i]!=charArray[j]){
                        dp[i][j] = false;
                    }else{
                        //如果头尾相等,得看下子回文是否相等
                        if(j-i<3){
                            dp[i][j] = true;
                        }else{
                            dp[i][j] = dp[i+1][j-1];
                        }
                        //如果是回文的话,得判断最长长度
                        if(dp[i][j] && (j-i+1) > maxLen){
                            maxLen = j - i +1;
                            begin = i;
                        }
                    }
                }
            }
            return s.substring(begin,begin+maxLen);
        }
    }
    public class Solution {

        public String longestPalindrome(String s) {
            int len = s.length();
            if (len < 2) {
                return s;
            }

            int maxLen = 1;
            int begin = 0;
            // dp[i][j] 表示 s[i..j] 是否是回文串
            boolean[][] dp = new boolean[len][len];
            // 初始化：所有长度为 1 的子串都是回文串
            for (int i = 0; i < len; i++) {
                dp[i][i] = true;
            }

            char[] charArray = s.toCharArray();
            // 递推开始
            // 先枚举子串长度
            for (int L = 2; L <= len; L++) {
                // 枚举左边界，左边界的上限设置可以宽松一些
                for (int i = 0; i < len; i++) {
                    // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                    int j = L + i - 1;
                    // 如果右边界越界，就可以退出当前循环
                    if (j >= len) {
                        break;
                    }

                    if (charArray[i] != charArray[j]) {
                        dp[i][j] = false;
                    } else {
                        if (j - i < 3) {
                            dp[i][j] = true;
                        } else {
                            dp[i][j] = dp[i + 1][j - 1];
                        }
                    }

                    // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                    if (dp[i][j] && j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        begin = i;
                    }
                }
            }
            return s.substring(begin, begin + maxLen);
        }
    }

    class SolutionManacher {
        public String longestPalindrome(String s) {
            int start = 0, end = -1;
            StringBuffer t = new StringBuffer("#");
            for (int i = 0; i < s.length(); ++i) {
                t.append(s.charAt(i));
                t.append('#');
            }
            t.append('#');
            s = t.toString();

            List<Integer> arm_len = new ArrayList<Integer>();
            int right = -1, j = -1;
            for (int i = 0; i < s.length(); ++i) {
                int cur_arm_len;
                if (right >= i) {
                    int i_sym = j * 2 - i;
                    int min_arm_len = Math.min(arm_len.get(i_sym), right - i);
                    cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
                } else {
                    cur_arm_len = expand(s, i, i);
                }
                arm_len.add(cur_arm_len);
                if (i + cur_arm_len > right) {
                    j = i;
                    right = i + cur_arm_len;
                }
                if (cur_arm_len * 2 + 1 > end - start) {
                    start = i - cur_arm_len;
                    end = i + cur_arm_len;
                }
            }

            StringBuffer ans = new StringBuffer();
            for (int i = start; i <= end; ++i) {
                if (s.charAt(i) != '#') {
                    ans.append(s.charAt(i));
                }
            }
            return ans.toString();
        }

        public int expand(String s, int left, int right) {
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                --left;
                ++right;
            }
            return (right - left - 2) / 2;
        }
    }


    @Test
    public void test(){
        Solution s1 = new Solution();
        SolutionC s2 = new SolutionC();

        /**
        "bbbab"
        */
        //int [] num1 = new int[]{1,3};
        //int [] num2 = new int[]{2};
        String huiwen = "asdfaswewaefasdfasdfabaddrawfcadf";
        System.out.println(s1.longestPalindrome(huiwen));
        Assertions.assertEquals(s1.longestPalindrome(huiwen),s2.longestPalindrome(huiwen));
    }
}

